home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / answrbok / 4_6.lha / 4_6 / 4_6c.c < prev    next >
C/C++ Source or Header  |  1993-08-08  |  3KB  |  126 lines
  1. * Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
  2. * The C++ Answer Book */
  3. * Tony Hansen */
  4. * All rights reserved. */
  5. / quick sort
  6. / Version 3
  7. / Based on "Algorithms" by Robert Sedgewick
  8. / Chapter 9, pp 103-113
  9.  
  10. include <swap.h>
  11.  
  12. / Global variables
  13. tatic char *a;
  14. tatic int size;
  15. tatic int (*cmpfn)(const void*,const void*);
  16. onst int unitcutoff = 16;
  17. tatic int cutoff;
  18.  
  19. / internal function to swap two
  20. / elements of the array
  21. nline void swapelem(char *ax, char *ay)
  22.  
  23.    for (int i = size; i-- > 0; )
  24. swap(*ax++, *ay++);
  25.  
  26.  
  27. include <string.h>
  28. / insertion sort to finish the job off
  29. tatic void inssort(int left, int right)
  30.  
  31.    char *savearea = new char[size];
  32.  
  33.    for (int i = left + size; i <= right; i += size)
  34. {
  35. memcpy(savearea, &a[i], size);
  36.  
  37. for (int j = i, k = j - size;
  38.      j > 0 && (*cmpfn)(&a[k], savearea) > 0;
  39.      j -= size, k -= size)
  40.     memcpy(&a[j], &a[k], size);
  41.  
  42. memcpy(&a[j], savearea, size);
  43. }
  44.  
  45.    delete savearea;
  46.  
  47.  
  48. / partition the array into two halves
  49. / after the partition,
  50. / K[left] < ... < K[i] < ... < K[right]
  51. / iqsort will then recursively sort
  52. / K[left] through K[i-1] and
  53. / K[i+1] through K[right]
  54. tatic int partition(int left, int right)
  55.  
  56.    // sort-three: sort left, middle and right elements
  57.    // to find partitioning element
  58.    int mid = (left + right) / size / 2 * size;
  59.  
  60.    if ((*cmpfn)(&a[left], &a[mid]) > 0)
  61. swapelem(&a[left], &a[mid]);
  62.  
  63.    if ((*cmpfn)(&a[left], &a[right]) > 0)
  64. swapelem(&a[left], &a[right]);
  65.  
  66.    if ((*cmpfn)(&a[mid], &a[right]) > 0)
  67. swapelem(&a[mid], &a[right]);
  68.  
  69.    int j = right - size;
  70.    swapelem(&a[mid], &a[j]);
  71.    int i = left;
  72.    char* v = &a[j];
  73.  
  74.    do  {
  75. do  {
  76.     i += size;
  77. } while ((*cmpfn)(&a[i], v) < 0);
  78.  
  79. do  {
  80.     j -= size;
  81. } while ((*cmpfn)(&a[j], v) > 0);
  82.  
  83. swapelem(&a[i], &a[j]);
  84.    } while (i < j);
  85.  
  86.    swapelem(&a[j], &a[i]);
  87.    swapelem(&a[i], &a[right - size]);
  88.    return i;
  89.  
  90.  
  91. / the secondary routine which will
  92. / do the actual sorting
  93. tatic void iqsort(int left, int right)
  94.  
  95.    while (right - left > cutoff)
  96. {
  97. int i = partition(left, right);
  98.  
  99. if (i - left > right - i)
  100.     {
  101.     iqsort(i + size, right);
  102.     right = i - size;
  103.     }
  104.  
  105. else
  106.     {
  107.     iqsort(left, i - size);
  108.     left = i + size;
  109.     }
  110. }
  111.  
  112.  
  113. oid qsort3(void *array, unsigned nel,
  114.     unsigned sz,
  115.     int (*cmpfunc)(const void*,const void*))
  116.  
  117.    a = (char*)array;        // set global variables
  118.    size = sz;
  119.    cmpfn = cmpfunc;
  120.    cutoff = sz * unitcutoff;
  121.  
  122.    int endindex = (nel - 1) * size;
  123.    iqsort(0, endindex);
  124.    inssort(0, endindex);
  125.  
  126.